package library;

import java.util.PriorityQueue;
import java.util.Queue;

public class Kruskals {

	Edge[] mst;
	int numEdgesUsed;
	double totalWeight;
	
	public void kruskals(Node[] nodes){
		Queue<Edge> queue = new PriorityQueue<Edge>();

		for (int j = 0; j < nodes.length; j++)
			for (int k = 0; k < j; k++)
				queue.add(new Edge(nodes[j].distance(nodes[k]),j,k));

		mst = new Edge[nodes.length]; 

		numEdgesUsed = 0;
		totalWeight = 0;
		for(int i = 0; i < nodes.length-1 && !queue.isEmpty(); ){
			Edge min = queue.poll();
			if(Find(nodes[min.n1])!=Find(nodes[min.n2])){
				i++;
				Union(nodes[min.n1],nodes[min.n2]);
				mst[numEdgesUsed] = min;
				totalWeight+=min.weight;
				numEdgesUsed++;
			}
		}
	}

	class Node{
		double x,y;
		int rank;
		Node parent;

		public Node (double x,double y){
			this.x = x;
			this.y = y;
			parent = this;
			rank = 0;
		}

		public double distance(Node o){
			return Math.sqrt((x-o.x)*(x-o.x)+(y-o.y)*(y-o.y));
		}
	}

	class Edge implements Comparable<Edge>{
		public double weight;
		public int n1;
		public int n2;

		public Edge(double weight, int n1, int n2) {
			this.weight = weight;
			this.n1 = n1;
			this.n2 = n2;
		}
		@Override
		public int compareTo(Edge e) {
			if (this.weight > e.weight)
				return 1;
			else if (this.weight < e.weight)
				return -1;
			else
				return 0;
		}
	}
	
	void Union(Node n, Node m){
		 Node nRoot = Find(n);
		 Node mRoot = Find(m);
		 
	     if (nRoot == mRoot)
	         return;

	     // x and y are not already in same set. Merge them.
	     if (nRoot.rank < mRoot.rank)
	    	 nRoot.parent = mRoot;
	     else if (nRoot.rank > mRoot.rank)
	    	 mRoot.parent = nRoot;
	     else{
	    	 mRoot.parent = nRoot;
	         nRoot.rank = nRoot.rank + 1;
	     }
	}

	//Get root node
	Node Find(Node n){
		if(n.parent==n)
			return n;
		else{
			n.parent = Find(n.parent);
			return n.parent;
		}
	}
}